The traditional attribute reduction method based on discernibility matrix is intuitive and easy to understand. However， its time and space complexities are high， so when dealing with large scale data or many conditional attributes， it will not be able to get the reduction result quickly. In order to solve the problem， the conditional discernibility was constructed based on the discernibility relation for attribute selection， and an attribute reduction algorithm based on conditional discernibility was proposed. In order to further accelerate the calculation of attribute importance and improve the efficiency of attribute reduction， according to the stability of frequency in the law of large numbers， the conditional discernibility was extended to local conditional discernibility by sampling， and an attribute reduction algorithm based on local conditional discernibility was proposed. It was theoretically proved that the conditional discernibility was stricter than the positive region in attribute selection. And this algorithm was compared with efficient Forward Attribute Reduction algorithm from Discernibility View （FAR-DV）， attribute reduction algorithm based on k-Nearest Neighbor attribute importance and Correlation Coefficient （K2NCRS） and Fast Positive Region reduction Algorithm based on positive region sort ascending decision table （FPRA）. Experimental results show that the proposed algorithm is similar to FAR-DV in attribute selection order， reduction rate and classification accuracy. Compared with the above three algorithms， the proposed algorithm has the reduction efficiency improved more than ten times. With the increase of data scale or conditional attributes， the reduction efficiency improvement of this algorithm is higher. It can be seen that the proposed algorithm has lower time and space complexities and is suitable for the attribute reduction of massive data.